package leecode

import (
	"strconv"
	"strings"
)

func restoreIpAddresses(s string) (result []string) {
	var backtracking func(startIndex int)
	path := make([]string, 0, len(s))
	backtracking = func(startIndex int) {
		if len(path) == 4 {
			//分隔三次 , 判断剩余的子串是否合法
			if startIndex == len(s) {
				temp := strings.Join(path, ".")
				result = append(result, temp)
			}
			return
		}
		for i := startIndex; i < len(s); i++ {
			if isLegal(s[startIndex : i+1]) {
				path = append(path, s[startIndex:i+1])
				backtracking(i + 1)
				path = path[:len(path)-1]
			} else {
				break // 不合法，直接结束本层循环
			}
		}
	}
	backtracking(0)
	return
}

func isLegal(s string) bool {
	arr := strings.Split(s, "")
	if len(arr) > 1 && arr[0] == "0" {
		return false
	}
	//字符串转整型
	temp, _ := strconv.Atoi(s)
	if temp >= 0 && temp <= 255 {
		return true
	}
	return false
}
